import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 先统计每个单词出现的次数
        Map<String, Integer> hash = new HashMap<>();
        for (String s : words) {
            hash.put(s, hash.getOrDefault(s, 0)+1);
        }
        // 创建小根堆
        PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> {
            // 比较两个字符串在哈希表中出现的次数
            int x = hash.get(a);
            int y = hash.get(b);
            if (x != y) { // 频次排序，小根堆
                return x-y;
            } else { // 字典排序，大根堆
                return b.compareTo(a);
            }
        });
        for (String s : hash.keySet()) {
            minHeap.offer(s);
            if (minHeap.size() > k) {
                // 说明堆顶元素一定不是前k个高频的单词
                minHeap.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            ret.add(minHeap.poll());
        }
        Collections.reverse(ret);
        return ret;
    }
}